package leetcode.sort;

/**
 */
public class Quicksort {

    public static void main(String[] args) {
        int [] arr = new int[]{1,3,2,5,8,5,7,4,2,10,19,13,12};
        new Quicksort().quickSort(arr);
        for (int i : arr) {
            System.out.print(i+" ");
        }
    }

    public void quickSort(int [] nums){
        quickSort(nums,0, nums.length-1);
    }

    private void quickSort(int [] nums,int l,int r){
        if(l>r)
            return;

        int i = partition(nums, l, r);
        quickSort(nums,l,i-1);
        quickSort(nums,i+1,r);
    }

    private int partition(int [] nums,int l,int r){
        int v = nums[l];

        int j=l;

        //[l...r]范围内
        for (int i = l+1; i <= r; i++) {
            if(nums[i] < v)
                swap(nums,i,++j);
        }
        swap(nums,j,l);//把标定点放在这个位置

        return  j;//标定点所处的位置
    }

    private void swap(int []nums,int i,int j){
        int t = nums[i];
        nums[i] = nums[j];
        nums[j] = t;
    }

}